{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# Continuous Linear Programming\n", "## Definition\n", "Continuous Linear Programming (CLP) spans a wide set of OR problems that can be modeled based on the following assumptions:\n", "\n", "- Unknown variables are continuous: The result variable and the decision variables can take any real value. Also, all the different coefficients can take any real value.\n", "- Objectives and constraints are linear expressions: The relationships between the variables are expressed as linear expressions. \n", "\n", "Clearly, CLP establishes a rather simplified model of real world problems. Many assumptions are needed to represent real problems as a set of linear expressions. Yet, CLP is a very powerful tool in OR and it can provide valuable insights to decision-making in different fields. The main reason is that, once these assumptions are taken, linear algebra provides valuable tools to find an optimal solution and analyse it. \n", "\n", "The main types of problems that will be covered in the CLP exercises belong to two problem types:\n", "\n", "- **Production mix:** Production mix problems help us determine the optimal allocation of resources in the production of good or services to either minimise costs or maximise profits\n", "- **Blending problems:** In blending problems, the objective is to find the optimal combination of components in a set of products that either minimise costs or maximise profits \n", "\n", "## Set up\n", "In CLP, the objective variable, noted as $z$, can take any real value:\n", "\n", "$z \\in \\mathbb{R}$\n", "\n", "The value of this unknown variable $z$ is a function of another set of unknowns, which are called decision variables and that represent our decisions. These decision variables are noted as $x_j$, where $j$ is an integer (sub)index that goes from 1 to $n$: \n", "\n", "$z = \\operatorname{f}(x_1, x_2, ..., x_n)$\n", "\n", "$x_1, x_2, ..., x_n \\in \\mathbb{R}$\n", "\n", "Therefore, we will have $n$ different decision variables, that are going to be continuous. And, in extension, z is also going to be continuous. So now we know from where does the C in CLP comes from. Next, in CLP, the function f is a linear function. \n", "What we want is to find the **optimal value** of $z$, which, depending on the type of problem will be either the maximum value (e.g. maximise profits) or the minimum value (e.g. minimise costs). \n", "\n", "Hence, we want to maximise or minimise $z$, which as we said is a linear function and therefore can be expressed as the sum of the product of the decision variables multiplied by a set of coefficients, which are noted as $c_1$ to $c_n$.\n", "\n", "$\\max or \\min z = \\operatorname{f}(x_1, x_2, ..., x_n) = c_1·x_1+c_2·x_2+...+c_n·x_n$\n", "\n", "Now, we know that linear functions do not have any absolute minimum or maximum, but the objective function is subject to a set of constraints, which are also linear functions of the decision variables, that is, the sum product of the decision variables times a set of coefficients noted as $a_{ij}$ must be less than, greater than, or equal to another coefficient noted as $b_j$. \n", "\n", "$s.t.$\n", "\n", "$a_{11}·x_1+a_{12}·x_2+...+a_{1n}·x_n \\leq b_1$\n", "\n", "$a_{21}·x_1+a_{22}·x_2+...+a_{2n}·x_n \\leq b_2$\n", "\n", "$...$\n", "\n", "$a_{m1}·x_1+a_{m2}·x_2+...+a_{mn}·x_n \\leq b_m$\n", "\n", "\n", "Note that coefficients $a$ have two sub-indexes, the second is equal to the index of the corresponding decision variable, and the first is equal to the sub-index of b.\n", "These new index $i$ ranges from 1 to $m$ and therefore, our optimisation function is subject to a set of $m$ constraints.\n", "We will refer to the expressions to the left of the inequality as the Left Hand Side (LHS), and to the other side of the relationship as the Right Hand Side (RHS).\n", "\n", "Now, note that we can use the sum operator to represent the objective function in a more compressed form, that is, the LHS is equal to the sum of the product of cj times xj for j equal to 1 up to n. Note that this is can also be represented as the dot product of two vectors, the vector $x$ with the decision variables and the vector $c$ of the coefficients.\n", "\n", "$\\max or \\min z = c_1·x_1+c_2·x_2+...+c_n·x_n = \\sum_{j=1}^{n}{c_j·x_j}=c·x$\n", "\n", "$x = [x_1, x_2, ..., x_n]^T$\n", "\n", "$c = [c_1, c_2, ..., c_n]^T$\n", "\n", "We can do the same transformations to the left hand sides of the constraints, expressing them as the sum product of the decision variables times the left hand side coefficients. And, we may as well express all the left hand sides of the constraints as the product of a matrix A that contains all the different coefficients times the decision variable vector.\n", "\n", "$\\max or \\min z = \\sum_{j=1}^{n}{c_j·x_j}$\n", "\n", "s.t.\n", "\n", "$\\sum_{j=1}^{n}{a_{1j}·x_j}\\leq b_1$\n", "\n", "$\\sum_{j=1}^{n}{a_{2j}·x_j}\\leq b_2$\n", "\n", "$...$\n", "\n", "$\\sum_{j=1}^{n}{a_{mj}·x_j}\\leq b_m$\n", "\n", "or\n", "\n", "$\\max or \\min z = c·x$\n", "\n", "$s.t.$\n", "\n", "$A·x \\leq b$\n", "\n", "$A = \\begin{bmatrix}\n", "a_{11} & a_{12} & ... & a_{1n}\\\\\n", "a_{21} & a_{22} & ... & a_{2n}\\\\\n", "...\\\\\n", "a_{m1} & a_{m2} & ... & a_{mn}\\\\\n", "\\end{bmatrix}$\n", "\n", "$b = [b_1, b_2, ..., b_m]$\n", "\n", "These alternative compact forms allow us to deal with problems with an arbitrary number of decision variables and an arbitrary number of constraints.\n", "\n", "## Problems\n", "This section further explains the types of problems that can be solved with CLP.\n", "\n", "### Production Mix Problems\n", "In production mix problems, the decision maker needs to create products to satisfy demand using limited resources. The objective is to maximise the profits, taking into account the demand and the limited availability of resources. \n", "Production mix problems represent the simplest form of optimization problem in operations research, where the objective is to maximise a utility function (in this case profits) bounded by a set of constraints. \n", "Normally, production mix problems are not found in real world applications, but rather, they are part of larger problems. \n", "\n", "#### Objective function\n", "Let us note the objective variable profits as $z$, expressed in a monetary unit (e.g. €). \n", "\n", "- $z$: profits in €. \n", "\n", "The decision maker needs to decide how many units of each product type to manufacture. Let us assume there are $n$ different products. Now, let us note the decision variables $x_j \\in \\mathbb{R}$ as the amount of product $j \\in [1, ..., n]$ to be produced, in a production unit: \n", "\n", "- $x_j$: Quantity of product $j$ to be produced in product units.\n", "\n", "The objective is to maximize profits. Let us note the profit per unit of product $j$ as $p_j$: \n", "\n", "- $p_j$: Profit per unit of product $j$ to be produced in €/unit.\n", "\n", "Now, the objective function is to maximise the sum of the product of the number of units produced times the profit per unit, for each product type: \n", "\n", "$\\max z = x_1*p_1 + x_2*p_2 + x_3*p_3 + ... + x_n*p_n = \\sum_{j=1}^{n}{x_j*p_j}$\n", "\n", "#### Demand constraints\n", "As mentioned above, there might be requirements on the demand. Let us note the demand of product j as $d_j$. The demand constraints will be of the type:\n", "\n", "$x_1 \\geq d_1$\n", "\n", "$x_2 \\geq d_2$\n", "\n", "...\n", "\n", "$x_n \\geq d_n$\n", "\n", "We can write the demand constraints in a compact form like: \n", "\n", "$x_j \\geq d_j \\quad \\forall j \\in [1, ..., n]$\n", "\n", "#### Availability constraints\n", "Different limited resources are used to produce each product. Let us assume that we have $m$ different resources. Let us note as $b_i$ as the quantity available of resource $i$ ($i \\in [1, ..., m]$), expressed in a given unit:\n", "\n", "- $b_i$: Availability of resource $i$ in resource unit.\n", " \n", " Further, to produce a unit of a product $j$ we will require a given amount of resource $i$. Let us note as $a_{ij}$ the requirement of resource $i$ to produce a unit of product $j$:\n", " \n", "- $a_{ij}$: Requirement of resource $i$ to produce a unit of product $j$ in resource unit / product unit. \n", " \n", "Then, for each resource $i$, we need to ensure that the total amount used is less or equal the total amount available. The amount used to produce a specific number of products will be the number of units products (e.g. $x_j$) multiplied by the amount required to produce one unit $x_{ij}$. If we sum across all products, we obtain the total amount used, which needs to be lower than the availability. Let's take the resource indexed 1 as an example: \n", " \n", "$x_1*a_{11} + x_2*a_{12} + ... + x_n*a_{1n} \\leq b_1$\n", "\n", "Note that we can write this down this constraint in a compact form like: \n", "\n", "$\\sum_{j=1}^{n}{x_j*a_{1j}}\\leq b_1$\n", "\n", "Now, we need to take into account the other resources:\n", "\n", "$\\sum_{j=1}^{n}{x_j*a_{2j}}\\leq b_2$\n", "\n", "$\\sum_{j=1}^{n}{x_j*a_{3j}}\\leq b_3$\n", "\n", "$...$\n", "\n", "$\\sum_{j=1}^{n}{x_j*a_{1j}}\\leq b_m$\n", "\n", "Note that we can write all this m equations in a compact form like:\n", "\n", "$\\sum_{j=1}^{n}{x_j*a_{ij}}\\leq b_i \\quad \\forall i \\in [1, ..., m]$\n", " \n", "That is, for every resource, we need to ensure that the sum of the quantities used to produce each type of product are less or equal than the total amount available. \n", " \n", "#### Summary\n", "Putting it all together, the generic formulation of the production mix problem as a CLP is:\n", " \n", " \n", "$\\max z = \\sum_{j=1}^{n}{x_j*p_j}$\n", "\n", "$\\text{s.t.}$\n", "\n", " $\\sum_{j=1}^{n}{x_j*a_{ij}}\\leq b_i \\quad \\forall i \\in [1, ..., m]$\n", "\n", "$x_j \\geq d_j \\quad \\forall j \\in [1, ..., n]$\n", "\n", "#### Examples\n", "The following exercises are instances of the production mix problem:\n", "\n", "- [Production mix](https://operations-research.readthedocs.io/en/latest/CLP/exercises/Production%20Mix%20Problem.html)\n", "- [Ski Patrol](https://operations-research.readthedocs.io/en/latest/CLP/exercises/Ski%20Patrol.html)\n", "- [The good carpenter](https://operations-research.readthedocs.io/en/latest/CLP/exercises/The%20Good%20Carpenter.html)\n", "\n", "### Blending Problems\n", "In blending problems, the decision maker needs to find the optimal blending (mixing or combination) of materials or resources to create **products** that satisfy a given demand. \n", "Each resource or material will have a different costs and therefore, in its primary form, the objective is to minimise the overall \n", "costs of the materials needed to satisfy the demand. Additionally, the required materials or resources needed may be subject to availability constraints (i.e. we cannot consider that the amount of materials or resources available is unlimited). \n", "\n", "#### Objective function\n", "Let us assume that we have $m$ different materials or resources to be considered in the problem and $n$ different products. \n", "\n", "Let us note the cost of material $i$ as $c_i \\quad i\\in[1, ..., m]$. Let us also note $x_{ij}$ the amount of resource or material $i$ used to produce products $j \\quad j \\in [1, ..., n]$. \n", "\n", "Note that these variables $x_{ij}$ represent our decision variables: We are looking for the optimal combination of resources or materials to manufacture our products. Note also that we have $m*n$ different decision variables (the combination of products and materials).\n", "\n", "With these definitions, our objective function can be defined as: \n", "\n", "$\\min z = \\sum_{i=1}^{m}\\sum_{j=1}^{n}c_i*x_{ij}$\n", "\n", "That is, the objective is to minimize the overall costs, which is the sum of the cost of the different materials needed to manufacture all our products. \n", "\n", "#### Availability constraints\n", "Since the amount of resources or materials available is limited, let us plug in the availability constraints, let as note as $a_m$ as the availability of the material or resource $m$. The total amount used to manufacture all products cannot exceed the availability of that specific material or resource. For instance, \n", "for material or resource 1, the sum of the amount used to manufacture the different products cannot exceed the availability $a_1$, that is: \n", "\n", "$\\sum_{j=1}^{n}{x_{1j}} \\leq a_1$\n", "\n", "The same applies to other material or resources:\n", "\n", "$\\sum_{j=1}^{n}{x_{2j}} \\leq a_2$\n", "\n", "$...$\n", "\n", "$\\sum_{j=1}^{n}{x_{mj}} \\leq a_m$\n", "\n", "We can write this set of constraints in a compact form as: \n", "\n", "$\\sum_{j=1}^{n}{x_{ij}} \\leq a_i \\quad i \\in [1, ..., m]$\n", "\n", "#### Demand constraint\n", "As mentioned above, we need to satisfy the demand for every product, which means that the total amount of a product that we need to manufacture needs to be greater or equal than its demand. Let us note $d_j$ as the demand for product $j$.\n", "\n", "Note that we do not have explicitly defined a decision variable for the quantity of each product to manufacture, but in terms of the blending problem, if all the materials are considered, it is equivalent to think of the total amount of a product as the total amount of the materials needed to manufacture a product. \n", "Hence, the demand constraints can be expressed as: \n", "\n", "$\\sum_{i=1}^{m}{x_{i1}} \\geq d_1$\n", "\n", "$\\sum_{i=1}^{m}{x_{i2}} \\geq d_2$\n", "\n", "$...$\n", "\n", "$\\sum_{i=1}^{m}{x_{in}} \\geq d_n$\n", "\n", "Note that we can express this set of constraints in a compact form as:\n", "\n", "$\\sum_{i=1}^{m}{x_{ij}} \\geq d_j \\quad j \\in [1, ..., n]$\n", "\n", "#### Additional requirements: Minimum amount\n", "We may find additional requirements in the problem definition, for instance, we may find a requirement for a minimum \n", "amount of an ingredient. Sometimes the requirement is expressed as a percentage or ratio of the total composition of the product. \n", "As an example, let us define that the minimum amount of material or resource 2 for product 3 needs to be 20%, or 0.2. \n", "If we are dealing with all the materials and resources used, we can again assume that the amount of material or resource $x_{23}$ needs to be at least 20% of the sum of all ingredients used to manufacture product 3, that is:\n", "\n", "$x_{23} \\leq 0.2*\\sum_{i=1}^{m}{x_{i3}}$\n", "\n", "We could bring all the dependant coefficients to the left-hand side and express this constraint as: \n", "\n", "$0 \\leq -1*x_{23} + 0.2*\\sum_{i=1}^{m}{x_{i3}}$\n", "\n", "$0 \\leq -0.8*x_{23} + 0.2*\\sum_{i=1, i\\neq2}^{m}{x_{i3}}$\n", "\n", "$0.8*x_{23} - 0.2*\\sum_{i=1, i\\neq2}^{m}{x_{i3}} \\geq 0$\n", "\n", "#### Combination of production mix and blending problems\n", "Instead of just minimizing the overall cost, our objective can be to maximise profit. This can be regarded as a combination \n", "of the production mix and blending problems. Let us define the unitary selling prices of our $n$ products as $[p_1, p_2, ..., p_n]$\n", "\n", "If we focus on one product, e.g. product 1, the profits can be calculated as the difference between the selling price \n", "and the cost obtained for the total amount of the products sold. Again, if we can assume that the total amount of \n", "ingredients is equal to the total amount of products, expressed in the same unit as the unitary selling price, the overall\n", "profits for product 1 can be expressed as: \n", "\n", "$p_1*\\sum_{i=1}^{n}{x_{i1}} - \\sum_{i=1}^{n}{c_i*x_{i1}}$\n", "\n", "Our objective is to maximize the overall profits, so we need to factor in the profits of the rest of the products with a sumatory:\n", "\n", "$\\max z = \\sum_{j=1}^{n}{p_j*\\sum_{i=1}^{n}{x_{ij}} - \\sum_{i=1}^{n}{c_i*x_{ij}}}$\n", "\n", "Now, we can re-arrange the terms of the summations as:\n", "\n", "$\\max z = \\sum_{j=1}^{n}{\\sum_{i=1}^{n}{(p_j - c_i)*x_{ij}}}$\n", "\n", "#### Examples\n", "The following exercises represent blending problem instances:\n", "\n", "- [Blending Problem](https://operations-research.readthedocs.io/en/latest/CLP/exercises/Blending%20Problem.html)\n", "- [Petroleum Blending](https://operations-research.readthedocs.io/en/latest/CLP/exercises/Petroleum%20Blending.html)\n", "- [Blending Craft Beer](https://operations-research.readthedocs.io/en/latest/CLP/exercises/Blending%20Craft%20Beer.html)\n", "\n", "## Standard Form\n", "Some algorithms like the Simplex need to operate with problems formulated in a standard form.\n", "Every CLP problem described in the set-up section can be converted to a standard form where: \n", "\n", "- The objective function is of type **maximise**\n", "- All the constraints are of type **equal**\n", "\n", "That is, any CLP problem can be expressed in the standard form as: \n", "\n", "$\\max z = \\sum_{i=1}^n{c_i*x_i} = c^T$\n", "\n", "s.t. \n", "$a_{11}·x_1+a_{12}·x_2+...+a_{1n}·x_n + s_1 = b_1$\n", "\n", "$a_{21}·x_1+a_{22}·x_2+...+a_{2n}·x_n + s_2 = b_2$\n", "\n", "$...$\n", "\n", "$a_{m1}·x_1+a_{m2}·x_2+...+a_{mn}·x_n + s_n = b_m$\n", "\n", "which can be expressed using a matrix product as: \n", "\n", "$A·x = b$\n", "\n", "and\n", "\n", "$x_i \\geq 0 \\quad \\forall i$\n", "\n", "### Conversion of minimization problems\n", "If we need to convert a problem where the objective function is of type minimize to the standard form, we need just need to make a change of variable: \n", "\n", "$z = -z*$\n", "\n", "With this change of variable the objective function: \n", "\n", "$\\min z = c·x$\n", "\n", "is equivalent to:\n", "\n", "$\\max z* = -c·x$\n", "\n", "And now the objective function is of type maximise. \n", "\n", "### Conversion of constraints and slack variables\n", "Note that we have introduced a new set of decision variables $s = [s_1, s_2, ..., s_n]$ used to make all the constraints of type equal. These are new \n", "variables that are introduced to change the type of constraint to a constraint of type equal. Imagine for instance that our problem\n", "has a constraint of type less or equal: \n", "\n", "$a_{11}·x_1+a_{12}·x_2+...+a_{1n}·x_n \\leq b_1$\n", "\n", "Since the left hand side is less or equal than the right hand side, we can make the left hand side equal to the right hand side by adding a non-negative \n", "variable $s_1$ to the left hand side: \n", "\n", "$a_{11}·x_1+a_{12}·x_2+...+a_{1n}·x_n + s_1 = b_1$\n", "\n", "Obviously, we need to add a non-negativity constraint to the new variable to make sure that both constraints are equivalent: \n", "\n", "$s_1 \\geq 0$\n", "\n", "Equivalently, if we have a constraint of type greater or equal, we can make the same modification, but now, the new variable needs to be lower or equal than zero to make the problem equivalent. For instance, let us consider without loss of generality that we have the following constraint in our problem:\n", "\n", "$a_{21}·x_1+a_{22}·x_2+...+a_{2n}·x_n \\geq b_2$\n", "\n", "This is equivalent to: \n", "\n", "$a_{21}·x_1+a_{22}·x_2+...+a_{2n}·x_n + s_2 = b_2$\n", "\n", "where: \n", "\n", "$s_1 \\leq 0$\n", "\n", "Also, if our constraint is of type equal, we do not need to introduce any change, but just to make sure we treat all constraints in the same way, let us introduce again a new variable: \n", "\n", "$a_{31}·x_1+a_{32}·x_2+...+a_{3n}·x_n = b_3$\n", "\n", "This is equivalent to: \n", "\n", "$a_{31}·x_1+a_{32}·x_2+...+a_{3n}·x_n + s_3 = b_3$\n", "\n", "where: \n", "\n", "$s_1 = 0$\n", "\n", "#### Slack variables\n", "These new variables are called **slack variables**, and they represent the difference between the left hand side and the right hand side. \n", "When slack variables are non-negative (meaning that the constraint is of type less or equal), they are called **surplus** variables. Note that \n", "normally these constraints represent limited resources, so the slack value will represent the surplus of resource that we have available in the optimal solution.\n", "When slack variables are non-positive (meaning that the constraint is of type greater or equal), they are called **excess** variables. Note that these types of constraints will normally represent additional requirements, \n", "so the value of the slack variable will represent the excess of the solution with respect to the requirement.\n", "When slack variables are zero, they are referred to **artificial variables**. Since they must be zero, they need to be treated differently by the solvers. \n", "\n", "### Conversion of negative decision variables\n", "Finally, note that in the standard form, all the decision variables need to be non-negative, we can achieve this with a change of variable: \n", "\n", "$x = x^i - x^{ii}$\n", "\n", "$x^i, x^{ii} \\in [0, \\inf]$\n", "\n", "That is, we replace the decision variable x by two non-negative decision variables, when $x^{ii}$ is greater than $x^i$, $x$ takes negative values. \n", "\n", "### Summary\n", "Now, in order to the standard form to hold, we need to plug in the new variables into the model. We first introduce the slack variables into our \n", "decision variable vector, so that it becomes: \n", "\n", "$x = [x_1, x_2, ..., x_n, s_1, s_2, ..., s_n]$\n", "\n", "Now, to make sure that there is no impact in the objective function, we multiply the non-zero slack variables by a factor of 0. Since artificial variables are \n", "equal to zero, we multiply them by an arbitrarily large negative number $-M$. This number needs to be introduced by algorithms such as the Simplex. Let us assume without loss of generality that we have $p$ non-zero slack variables and $k$ artificial variables. Let us note artificial variables as \n", "$a_1$, $a_2$, ..., $a_k$. Our objective function becomes: \n", "\n", "$\\max z = \\sum_{i=1}^n{c_i*x_i} + 0*s_1 + 0*s_2 + ... + 0*s_p - M*a_1 - M*a_2 + ... - M*a_k$\n", "\n", "And the constraints: \n", "\n", "$a_{11}·x_1+a_{12}·x_2+...+a_{1n}·x_n + s_1 + 0*s_2 + ... + 0*s_p + 0*a_1 + 0*a_2 + ... + 0*a_k= b_1$\n", "\n", "$a_{21}·x_1+a_{22}·x_2+...+a_{2n}·x_n + 0*s_1 + 0_2 + ... + 0*s_p + 0*a_1 + 0*a_2 + ... + 0*a_k = b_2$\n", "\n", "$...$\n", "\n", "$a_{p1}·x_1+a_{p2}·x_2+...+a_{pn}·x_n + 0*s_1 + 0*s_2 + ... + s_p + 0*a_1 + 0*a_2 + ... + 0*a_k = b_p$\n", "\n", "$a_{(p+1)1}·x_1+a_{(p+1)2}·x_2+...+a_{n}·x_n + 0*s_1 + 0*s_2 + ... + 0*s_p + a_1 + 0*a_2 + ... + 0*a_k = b_{p+1}$\n", "\n", "$a_{(p+2)1}·x_1+a_{(p+2)2}·x_2+...+a_{(p+2)n}·x_n + 0*s_1 + 0*s_2 + ... + 0*s_p + 0*a_1 + *a_2 + ... + 0*a_k = b_{p+2}$\n", "\n", "$...$\n", "\n", "$a_{m1}·x_1+a_{m2}·x_2+...+a_{mn}·x_n + 0*s_1 + 0*s_2 + ... + 0*s_p + 0*a_1 + 0*a_2 + ... + 1*a_k = b_m$\n", "\n", "### Standard tabular representation\n", "Note that we can express the standard form as stated at the beginning of this section as: \n", "\n", "$\\max z = c·x$\n", "\n", "s.t.\n", "\n", "$A = b$\n", "\n", "where\n", "\n", "$x = [x_1, x_2, ..., x_n, s_1, s_2, ..., s_p, a_1, a_2, ..., a_k]^T$\n", "\n", "$c = [c_1, c_2, ..., c_n, 0, ...0, -M, ..., -M]^T$\n", "\n", "$$\n", "A = \\begin{bmatrix}\n", "a_{11} & a_{12} & ... & a_{1n} & 1 & 0 & ... & 0\\\\\n", "a_{21} & a_{22} & ... & a_{2n} & 0 & 1 $ ... & 0\\\\\n", "...\\\\\n", "a_{m1} & a_{m2} & ... & a_{mn} & 0 & 0 & ... & 1\\\\\n", "\\end{bmatrix}$$\n", "\n", "$x$ and $c$ are two $n+m$ vectors and $A$ is a mx(n+m) matrix where the right most n columns represent the original LHS coefficients and the right most n columns represent the nxn identity matrix.\n", "\n", "Now, if we move all the dependent terms to the LHS, the objective function becomes: \n", "\n", "$\\ z - c_1*x_1 - c_2*x_2 - ... - c_n*x_n - 0*s_1 - 0*s_2 + ... - 0*s_p + M*a_1 + M*a_2 + ... + M*a_k = 0$\n", "\n", "We can write all the coefficients in a data frame where each column represents the coefficients of a variable and each row represents an equation: \n", "\n", "| z | $x_1$ | $x_2$ | ... | x_n | s_1 | s_2 | ... | s_p | a_1 | a_2 | ... | a_k | RHS |\n", "| --- | -------- | -------- | --- | -------- | --- | --- | --- | --- | --- | --- | --- | --- | ---- |\n", "| 1 | $-c_1$ | $-c_2$ | ... | $-c_n$ | 0 | 0 | ... | 0 | -M | -M | ... | -M | 0 |\n", "| 0 | $a_{11}$ | $a_{12}$ | ... | $a_{1n}$ | 1 | 0 | 0 | ... | 0 | 0 | ... | 0 | $b_1 |\n", "| 0 | $a_{21}$ | $a_{22}$ | ... | $a_{2n}$ | 0 | 1 | 0 | ... | 0 | 0 | ... | 0 | $b_2 |\n", "| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |\n", "| 0 | $a_{m1}$ | $a_{m2}$ | ... | $a_{mn}$ | 0 | 0 | 0 | ... | 0 | 0 | ... | 1 | $b_m |\n", "\n", "This representation of the problem is called the standard tabular form. \n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.6" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 0 }